package com.camus.verify.algorithm.impl;

import java.math.BigDecimal;
import java.util.Arrays;
import java.util.Comparator;

import com.camus.utils.BigDecimalUtils;
import com.camus.verify.algorithm.MatchTarget;
import com.camus.verify.algorithm.SubsetAlgorithm4BigDecimal;

public class SubsetAlgorithmOfSortPruningRecursion4BigDecimal implements SubsetAlgorithm4BigDecimal {

	@Override
	public MatchTarget[] findSubsetWithinRange(MatchTarget[] candidateArr, BigDecimal lower, BigDecimal upper) {
		// 先排序，方便后面有针对性地剪枝
		Arrays.sort(candidateArr, Comparator.comparing(MatchTarget::getTarget, BigDecimal::compareTo));

		int len = candidateArr.length;
		// 前缀和
		BigDecimal[] prefixSumArr = new BigDecimal[len];
		prefixSumArr[0] = candidateArr[0].getTarget();
		for (int i = 1; i < len; i++) {
			prefixSumArr[i] = prefixSumArr[i - 1].add(candidateArr[i].getTarget());
		}

		// fail fast
		BigDecimal min = candidateArr[0].getTarget();
		BigDecimal max = candidateArr[len - 1].getTarget();
		BigDecimal sum = prefixSumArr[len - 1];
		if (min.compareTo(BigDecimal.ZERO) >= 0) {
			// 所有元素都是正数
			if (BigDecimalUtils.isWithinRange(min, upper, lower) == 1) {
				// 且最小元素大于上边界
				return null;
			}
			if (BigDecimalUtils.isWithinRange(sum, upper, lower) == -1) {
				// 且所有元素之和仍然小于下边界
				return null;
			}
		}
		if (max.compareTo(BigDecimal.ZERO) <= 0) {
			// 所有元素都是负数，
			if (BigDecimalUtils.isWithinRange(max, upper, lower) == -1) {
				// 且最大元素小于下边界
				return null;
			}
			if (BigDecimalUtils.isWithinRange(sum, upper, lower) == 1) {
				// 且所有元素和仍然大于上边界
				return null;
			}
		}

		// 逐层递归
		MatchTarget[] subsetArr = findSubsetWithinRange(candidateArr, lower, upper, prefixSumArr, new boolean[len], 0,
				BigDecimal.ZERO);
		return subsetArr;
	}

	public MatchTarget[] findSubsetWithinRange(MatchTarget[] candidateArr, BigDecimal lower, BigDecimal upper,
			BigDecimal[] prefixSumArr, boolean[] flagArr, int nextIdx, BigDecimal curSum) {
		SubsetAlgorithm4BigDecimal.counter.get().getAndIncrement();
		// 递归终止条件
		if (BigDecimalUtils.isWithinRange(curSum, upper, lower) == 0) {
			return filterSubset(candidateArr, flagArr);
		}
		int len = candidateArr.length;
		if (nextIdx >= len) {
			return null;
		}

		// 根据数据升序的特点，提前结束递归调用的情况
		if (candidateArr[nextIdx].getTarget().compareTo(BigDecimal.ZERO) >= 0) {
			// 剩余所有元素都是正数
			if (BigDecimalUtils.isWithinRange(curSum, upper, lower) == 1) {
				// 当前已选择的元素之和已经大于目标和上边界
				return null;
			}
			// curSum+区间和的最大值
			BigDecimal maxSum = prefixSumArr[len - 1];
			if (nextIdx > 0) {
				maxSum = maxSum.subtract(prefixSumArr[nextIdx - 1]);
			}
			if (BigDecimalUtils.isWithinRange(curSum.add(maxSum), upper, lower) == -1) {
				// 当前已选择的元素之和+剩余的所有元素之和仍然小于目标和下边界
				return null;
			}
		}

		// 处理当层逻辑
		// 对于candidateArr[nextIdx]，有两种选择：a.包含 b.不包含
		// a.结果集中包含当前元素
		flagArr[nextIdx] = true;
		MatchTarget[] result = findSubsetWithinRange(candidateArr, lower, upper, prefixSumArr, flagArr, nextIdx + 1,
				curSum.add(candidateArr[nextIdx].getTarget()));
		if (result != null) {
			return result;
		}

		// b.结果集中不包含当前元素
		flagArr[nextIdx] = false;
		return findSubsetWithinRange(candidateArr, lower, upper, prefixSumArr, flagArr, nextIdx + 1, curSum);
	}

	private MatchTarget[] filterSubset(MatchTarget[] candidateArr, boolean[] flagArr) {
		int len = candidateArr.length;

		int size = 0;
		for (int i = 0; i < len; i++) {
			if (flagArr[i]) {
				size++;
			}
		}

		MatchTarget[] subsetArr = new MatchTarget[size];
		for (int i = len - 1; i >= 0; i--) {
			if (flagArr[i]) {
				subsetArr[--size] = candidateArr[i];
			}
		}
		return subsetArr;
	}

}
